Electronic data, including text, graphics, voice, multimedia, and other strings of symbols, may be represented by binary codes that compress such information. Such compression reduces the number of bits required for storing and/or transmitting the data. Binary codes of different or variable lengths may be used to represent different symbols in a bitstream of data. According to some binary code compression techniques, more frequently occurring symbols within a bitstream are represented with shorter codes, and less frequently occurring codes are represented using longer codes. Such a scheme may be referred to as Variable Length Coding (VLC).
One type of VLC scheme may involve Huffman codes. Huffman codes may be used, for example, in digital video compression and information retrieval for video coding standards such as Microsoft™ Windows Media, MPEG-2, MPEG-4, H.263, H.264, and other such standards employing VLC.
Huffman codes employ variable length code words. Thus, in some Huffman decoding implementations, a bitstream segment of the incoming bitstream may be matched against the contents of a Look-Up-Table (LUT) according to a “nibble-by-nibble” approach. For example, a decoder may look into a first, fixed size nibble and try to match it with first table entries in a Huffman decoding table. If no match is found, the decoder may look into a second, fixed size nibble and try to match with second table entries, and so forth. Such an approach may be conceptualized as a hashing function.
For longer Huffman code words (e.g., 23 bit code words), however, such nibbling schemes may take up to 6 steps and/or clocks to match the longest Huffman codewords. Longer code words, in such a nibbling scheme, may limit decoding throughput.
To reduce such throughput limitations, tables of Huffman code words may be remapped into compact tables. Such compact tables may provide for decoding through the detection of run lengths of a particular binary value (e.g., 0 or 1). Run length detection may be performed more rapidly than nibble-by-nibble approaches. Such detection may be implemented with dedicated hardware logic, software (e.g., a leading zero detector (LZD)), or combinations thereof. Moreover, longer runs of binary values may facilitate rapid detection, by dedicated hardware logic or a software detector (e.g., a leading zero detector (LZD)) or some combination thereof.
Generation of compact tables may be performed manually. However, such techniques are laborious and prone to creating table errors.